package 牛客.动态规划;

public class 力扣343整数拆分 {
    public int integerBreak(int n) {
        if (n==1) {
            return 0;
        }
        if (n==2) {
            return 1;
        }
        int[] dp=new int[n+1];
        //dp[i]代表的是 整数为i时，拆分i得到的最大乘积
        //dp[i]=Max（j*(i-j) , j*dp[i-j]）
        dp[0]=0;
        dp[1]=0;
        for (int i = 2; i <dp.length; i++) {
            int curMax=0;
            for (int j = 1; j <=i-1; j++) {
                curMax=Math.max(curMax,Math.max(j*(i-j),j*dp[i-j]));
            }
            dp[i]=curMax;
        }
        return dp[n];

    }
}
